#include <bits/stdc++.h>
using namespace std;

// stack b c  <-- a

class Solution {
public:
    string removeDuplicateLetters(string s) {
        map<char,int> mpFreq;
        for(auto c:s) mpFreq[c]++;
        string stk;
        for(auto c:s){
            if(stk.find(c)!=string::npos){
                mpFreq[c]--;
                continue;
            }
            while( !stk.empty() && stk.back() > c
                   && mpFreq[stk.back()]>1) {
                mpFreq[stk.back()]--;
                stk.pop_back();
            }
            stk.push_back(c);
        }
        return stk;
    }
};
